package main

import "fmt"

//0-1背包
//dp[i][w]表示：对于前i个物品，当前背包的容量为w时，这种情况下可以装下的最大价值是dp[i][w]。
//如果你没有把这第`i`个物品装入背包，那么很显然，最大价值`dp[i][w]`应该等于`dp[i-1][w]`。
//如果你把这第`i`个物品装入了背包，那么`dp[i][w]`应该等于`dp[i-1][w-wt[i-1]] + val[i-1]`。

func backpack(weight, value []int, bagWeight int) int {
	n := len(weight)
	//定义dp数组
	dp := make([][]int, n+1) //dp[i]：物品总数
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, bagWeight+1)
	}
	for i := 1; i <= n; i++ { //i的范围是[1,3]
		//由于i是从1开始的，所以 weight和value的索引是i-1时表示第i个物品的价值和重量。
		for w := 1; w <= bagWeight; w++ { //w的范围是[1,4]
			if w < weight[i-1] { //如果剩余背包重量 小于 第i个物品的重量
				dp[i][w] = dp[i-1][w]
			} else {
				dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]]+value[i-1])
			}
		}
	}
	return dp[n][bagWeight]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	weight := []int{35, 18, 11, 16, 3}
	value := []int{30, 28, 10, 19, 5}
	fmt.Println(backpack(weight, value, 60))
}
